package cnki.kg.algorithm;

import org.junit.jupiter.api.Test;

public class MaxProfit {

    @Test
    public void test() {
        int[] arr = new int[]{7, 1, 5, 3, 6, 4};
        int res2 = maxProfit(arr);
        System.out.println(res2);
    }

    public int maxProfit(int prices[]) {
        int maxprofit = 0;
        // 枚举所有发生一次交易的股价差
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                maxprofit = Math.max(maxprofit, prices[j] - prices[i]);
            }
        }

        return maxprofit;
    }

    public int maxProfit2(int prices[]) {
        int len = prices.length;
        int res = 0;
        // 前一天卖出可以获得的最大利润
        int pre = 0;
        for (int i = 1; i < len; i++) {
            // 利润差
            int diff = prices[i] - prices[i - 1];
            // 状态转移方程：第i天卖出可以获得的最大利润 = 第i-1天卖出的最大利润 + 利润差
            pre = Math.max(pre + diff, 0);
            res = Math.max(res, pre);
        }
        return res;
    }
}
